درسنامه آموزشی فصل سوم ریاضیات گسسته کلاس دوازدهم ریاضی
درس 1: مباحثی در ترکیبیّات
یادآوری و تکمیل
در سالهای قبل با ابزارهایی همچون اصل جمع و اصل ضرب برای شمارش آشنا شده و با بعضی از تکنیکها و روشهای شمارش مانند تبدیل r شیء از n شیء (انتخاب r شیء که ترتیب انتخاب آنها مهم باشد) و ترکیب r شیء از n شیء (انتخاب r شیء که ترتیب انتخاب آنها مهم نباشد) نیز آشنایی داشته و از آنها در حل مسائل شمارشی استفاده کردهاید.
گاهی اوقات برای شمارش در حالتهای خاص باید از روشهایی همچون دستهبندی اشیا یا تقسیم کل جایگشتهای ممکن بر تعداد حالتهایی که تکراری یا بیاثر محسوب میشوند، استفاده کنیم.
در این درس با توجه به طرح و حل مثالهایی، شما با این روشها آشنا خواهید شد.
مثال: فرض کنید میخواهیم با سه حرف «چ»، «پ» و «ژ» و ارقام 2، 3، 4 و 5 یک رمز شامل 7 کاراکتر تشکیل دهیم، مطلوب است:
الف) تعداد کل رمزهایی که میتوان تشکیل داد.
ب) تعداد رمزهایی که در هر یک از آنها همواره حروف کنار یکدیگرند.
پ) تعداد رمزهایی که در هر یک از آنها همواره ارقام کنار یکدیگرند.
ت) تعداد رمزهایی که در هر یک از آنها همواره ارقام کنار هم و حروف نیز کنار هم باشند.
حل:
الف) 3 حرف و 4 رقم روی هم 7 شیء متمایز بوده و به $7!$ طریق میتوانند کنار هم قرار گیرند و رمز تولید کنند.
ب) کافی است ابتدا سه حرف را با هم یک شیء در نظر بگیریم و آنها را با 4 رقم داده شده روی هم 5 شیء فرض کنیم. در اینصورت $5!$ جایگشت دارند؛ در هر جایگشت، سه حرف داده شده هم در عین حال که کنار هم هستند $3!$ جایگشت دارند و لذا طبق اصل ضرب تعداد کل رمزهای موردنظر برابر است با $5!\times 3!$
پ) مشابه قسمت (ب) ابتدا 4 رقم داده شده را یک شیء فرض میکنیم که با 3 حرف مفروض روی هم 4 شیء بوده و $4!$ جایگشت داشته و در هر جایگشت 4 رقم داده شده هم $4!$ در کنار هم جایگشت دارند، لذا تعداد رمز مورد نظر، طبق اصل ضرب عبارت است از $4!\times 4!$
ت) حروف را یک شیء و ارقام را نیز با هم یک شیء فرض میکنیم که روی هم دو شیء شده و $3!$ حروف در کنار هم و $4!$ نیز ارقام کنار هم جایگشت دارند که طبق اصل ضرب تعداد رمزهای مورد نظر عبارت است از $2!\times 3!\times 4!$
ما برای حل این مثال از دستهبندی اشیا استفاده کردیم.
حال مسئلهای را طرح و حل میکنیم ولی هیچ توضیحی برای حل آن نمیدهیم تا شما خودتان راه حل این مسئله را توضیح دهید.
مثال: 5 دانشآموز پایهٔ دوازدهم و 4 دانشآموز پایهٔ یازدهم به چند طریق میتوانند کنار هم (در یک ردیف) قرار بگیرند اگر بخواهیم:
الف) همواره دانشآموزان هر پایه کنار هم باشند.
ب) بهصورت یک درمیان قرار بگیرند (هیچ دو دانشآموز همپایه کنار هم نباشند).
پ) اگر دانشآموزان پایهٔ یازدهم نیز 5 نفر باشند، به چند طریق میتوان آنها را بهصورت یکدرمیان قرار داد؟
$2!\times 3!\times 4!$ (الف
$5\,\,4\,\,4\,\,3\,\,3\,\,2\,\,2\,\,1\,\,1\,\to 5\times 4\times 4\times 3\times 3\times 2\times 2=5!\times 4!$ (ب
$(5!\times 5!)\times 2$ (پ
جایگشتهای با تکرار
گاهی اوقات چند شیء تکراری یا یکسان در بین اشیا یافت میشود. در این حالت تعداد جایگشتهای این اشیا با تعداد جایگشتها در حالتیکه هیچ دو شیء یکسانی در بین اشیا نباشد، متفاوت بوده و به نظر میرسد کمتر باشد. بهعنوان مثال تعداد جایگشتهای سه حرف b ،a و c برابر با $3!=6$ است ولی تعداد جایگشتهای سه حرف a ،a و c برابر با 3 است $(baa\,,\,aba\,,\,aab)$ درواقع چون جابهجایی دو حرف a حالت جدیدی تولید نمیکند و حالت تکراری بهحساب میآید پس در واقع میبایست تعداد کلّ جایگشتها را بر تعداد حالتهایی که دو حرف تکراری میتوانند جابهجا شوند یعنی $2i$ تقسیم کنیم، پس پاسخ این سؤال $\frac{3i}{2i}=3$ است.
چون دو حرف a به $2i$ طریق میتوانند با هم جابهجا شوند و این تعداد جابهجایی بهصورت ضربی در $3i$ محاسبه شده و نباید محاسبه میشد، پس باید با تقسیم $3i$ بر $2i$ از عملیات ضربی خارج شود.
کار در کلاس (صفحهٔ 58 کتاب درسی)
محاسبه کنید با ارقام 2، 1، 1 و 1 چند رمز چهار رقمی میتوان نوشت؟
اگر 4 رقم متمایر بودند جواب این سؤال $4i$ بود ولی چون در این $4i$ و بهصورت ضربی، $3i$ حالت ممکن برای بچهها محاسبه شده و نباید محاسبه میشد، لذا کافی است برای رسیدن به جواب، تعداد کل حالتها را بر تعداد حالتهایی که رمز 4 رقمی جدید تولید نمیشود تقسیم کنیم یعنی پاسخ، $\frac{4!}{....}=....$ است.
تذکر: هرگاه n شیء مفروض باشند و در بین آنها k شیء تکراری یا مشابه وجود داشته باشد، برای محاسبهٔ تعداد جایگشتهای این n شیء ابتدا آنها را متمایز کرده و جایگشتهای آنها را حساب میکنیم و سپس حاصل را بر جایگشتهای اشیای تکراری (بهدلیل ورود در محاسبات بهصورت ضربی) تقسیم میکنیم؛ یعنی این تعداد برابر است با: $\frac{n!}{k!}$
با همین استدلال میتوان قضیهٔ زیر را، که به آن قضیهٔ جایگشت با تکرار میگوییم، بیان کرد:
قضیهٔ جایگشت با تکرار: اگر n شیء مفروض باشند، بهطوریکه ${{n}_{1}}$تای آنها از نوع اول و یکسان و ${{n}_{2}}$تای آنها از نوع دوم و یکسان و ... و ${{n}_{k}}$تای آنها از نوع kام و یکسان باشند، در اینصورت تعداد کل جایگشتهای این اشیا برابر است با:
$\frac{n!}{{{n}_{1}}!\times {{n}_{2}}!\times ...\times {{n}_{k}}!}$
مثال: با ارقام 5، 4، 4، 2، 3، 2، 2، 1 و 1 چند عدد 9 رقمی میتوان نوشت؟
حل: طبق قضیهٔ جایگشت با تکرار
مثال: 9 نفر به چند طریق میتوانند در سه اتاق 2 نفره، 3 نفره و 4 نفره واقع در یک هتل اسکان یابند؟
حل: کل جایگشتهای 9 نفر عبارت است از $9i$ است که چون دو نفری که در اتاق دو نفره هستند با جابهجایی آنها مجدداً همان دو نفر در همان اتاق بوده و حالت جدیدی تولید نمیشود و نیز جابهجایی سه نفر و چهار نفر در اتاقهای سه نفره و چهار نفره حالت جدیدی تولید نمیکند و تعداد این جایگشتهای بیاثر برای دو نفر، سه نفر و چهار نفر بهترتیب $2i$، $3i$ و $4i$ است، پس پاسخ این سؤال طبق قضیه برابر است با $\frac{9!}{2!\times 3!\times 4!}$. این مثال به روشی دیگر با استفاده از ترکیب برای انتخاب افراد (جابهجایی افراد انتخاب شده برای اتاقها مهم نیست):
فعالیت (صفحهٔ 59 کتاب درسی)
شخصی وارد یک گل فروشی میشود و میخواهد دسته گلی شامل سه شاخه گل، از بین سه نوع گل مریم، رُز و میخک، انتخاب کند. (از هر نوع گل به تعداد فراوان موجود است)
1- هر سطر جدول زیر یک انتخاب را نمایش میدهد، شما این جدول را کامل کنید.
| دسته گل انتخابی | مریم | رز | میخک | |
| 1 | یک شاخه گل مریم، یک شاخه گل رز و یک شاخه گل میخک | * | * | * |
| 2 | دو شاخه گل میخک و یک شاخه گل مریم | * | ** | |
| 3 | سه شاخه گل رز | ...... | *** | ....... |
| 4 | ......................... | ...... | ** | * |
| 5 | ......................... | *** | ...... | ...... |
| 6 | ......................... | ** | ...... | * |
| 7 | دو شاخه گل مریم و یک شاخه گل رز | ...... | ...... | ...... |
| 8 | سه شاخه گل میخک | ...... | ...... | ...... |
| 9 | دو شاخه گل میخک | ...... | ...... | ...... |
| 10 | ......................... | ...... | ...... | ...... |
همانطور که مشاهده میکنید برای جدا کردن سه نوع گل از دو خط عمودی و برای مشخص کردن تعداد انتخابها از هر نوع گل از ٭ استفاده شده است.
2- آیا در هر حالت از حالتهای 1 تا 10 جابهجایی ستارهها با هم دسته گل جدیدی تولید میکند؟ جابهجایی دو خط عمودی با هم چطور؟
3- با توجه به قضیهٔ جایگشت با تکرار تعداد کلّ جایگشتهای این 5 شیء (3 ستاره و 2 خط عمودی) را بهدست آورید.
$=\frac{5!}{....\times ....}=\left( \begin{matrix}
5 \\
2 \\
\end{matrix} \right)=\left( \begin{matrix}
3+2 \\
2 \\
\end{matrix} \right)$ تعداد جایگشتها
4- این مسئله را در حالت کلّی و برای انتخاب دلخواه n شاخه گل از بین k نوع گل بررسی کنید.
$n$ = تعداد ستارهها = تعداد شاخه گلهای انتخابی
....... = تعداد خطهای عمودی برای جدا کردن k نوع گل
....... = تعداد کل اشیا (شامل ستارهها و خطهای عمودی)
$ = \frac{{\left[ {n + \left( {k - 1} \right)!} \right]}}{{n! \times ....}} = \left( {\begin{array}{*{20}{c}} {n + (k - 1)}\\ {k - 1} \end{array}} \right)$ تعداد کل جایگشتها
مثال: به چند طریق میتوان از بین 4 نوع گل، دسته گلی شامل 8 شاخه گل را به دلخواه انتخاب کرد؟
حل:
$=k=4$ انواع گل
$=n=8$ تعداد شاخه گل انتخابی به دلخواه
$\Rightarrow \left( \begin{matrix}
n+k+1 \\
k-1 \\
\end{matrix} \right)=\left( \begin{matrix}
11 \\
3 \\
\end{matrix} \right)=\frac{11!}{3!\times 8!}$ فعالیت قبل
مثال: به چند طریق میتوان دسته گلی شامل 9 شاخه گل را از بین 4 نوع گل انتخاب کرد، به شرط آنکه از هر نوع گل حداقل 1 شاخه انتخاب شود؟
حل: ابتدا 1 شاخه (به اجبار) از هر نوع گل برمیداریم. $9-4=5$ شاخه گل باقیمانده را به دلخواه از بین 4 نوع گل انتخاب میکنیم:
$k=4$
$\Rightarrow n=9-4=5$ تعداد انتخابهای دلخواه
$\Rightarrow \left( \begin{matrix}
n+k-1 \\
k-1 \\
\end{matrix} \right)=\left( \begin{matrix}
8 \\
3 \\
\end{matrix} \right)$ تعداد حالتهای مطلوب
فعالیت (صفحهٔ 60 کتاب درسی)
میخواهیم تعداد انتخابهای دلخواه 7 شاخه گل از بین سه نوع گل را مشخص کنیم. اگر فرض کنیم ${{x}_{1}}$ تعداد انتخابها از گل نوع اول و ${{x}_{2}}$ تعداد انتخابها از گل نوع دوم و ${{x}_{3}}$ تعداد ……………… باشد، در اینصورت میبایست جمع انتخابها از سه نوع گل، برابر با 7 باشد یعنی ${{x}_{1}}+{{x}_{2}}+....=....$ با توجه به اینکه هر جواب صحیح و نامنفی این معادله نشاندهندهٔ یک انتخاب هفتتایی از سه نوع گل بوده و برعکس هر انتخاب هفتتایی از این سه نوع گل یک جواب صحیح و نامنفی برای این معادله است جدول زیر را کامل کرده و سپس تعداد جوابهای معادله را بهدست آورید.
| ${{x}_{1}}+{{x}_{2}}+{{x}_{3}}=7$ | تعداد انتخابها از گل نوع سوم ${{x}_{3}}$ | تعداد انتخابها از گل نوع سوم ${{x}_{2}}$ | تعداد انتخابها از گل نوع سوم ${{x}_{1}}$ |
| $1+0+6=7$ | 6 | 0 | 1 |
| $1+1+5=7$ | 5 | 1 | 1 |
| $4+2+1=7$ | .... | .... | |
| .......... | .... | 7 | |
| .......... | 2 | 4 | |
| .......... | .... | .... |
تعداد جوابهای صحیح و نامنفی معادلهٔ ${{x}_{1}}+{{x}_{2}}+{{x}_{3}}=7$ برابر است با تعداد انتخابهای دلخواه 7 شاخه گل از بین سه نوع گل یعنی،
$\left( \begin{matrix}
n+k-1 \\
k-1 \\
\end{matrix} \right)=\left( \begin{matrix}
.... \\
.... \\
\end{matrix} \right)=....$
با توجه به فعالیت قبل میتوان گفت:
تعداد جوابهای صحیح و نامنفی معادلهٔ ${{x}_{1}}+{{x}_{2}}+{{x}_{k}}=n$ برابر است با تعداد انتخابهای دلخواه n شاخه گل از بین k نوع گل یعنی برابر است با
$\left( \begin{matrix}
n+k-1 \\
k-1 \\
\end{matrix} \right)$
کار در کلاس (صفحهٔ 61 کتاب درسی)
1- معادلهٔ ${{x}_{1}}+{{x}_{2}}+{{x}_{3}}=7$ چند جواب صحیح مثبت دارد؟
(راهنمایی: مثال را ملاحظه کنید، از هر نوع گل حداقل 1 شاخه انتخاب شود.)
2- نشان دهید تعداد جوابهای صحیح و مثبت معادلهٔ ${{x}_{1}}+{{x}_{2}}+....{{x}_{k}}=n$ برابر است با $\left( \begin{matrix}
n-1 \\
k-1 \\
\end{matrix} \right)$.
(راهنمایی: ابتدا از هر نوع گل 1 شاخه برداشته ولذا تعداد انتخابهای دلخواه به $(n-k)$ تقلیل مییابد و ...)
3- معادلهٔ ${{x}_{1}}+{{x}_{2}}+....{{x}_{5}}=14$ چند جواب صحیح و نامنفی دارد به شرط آنکه ${{x}_{1}}\gt 1$ و ${{x}_{3}}\gt 3$ باشد؟
4- معادلهٔ ${{x}_{1}}+{{x}_{2}}+....{{x}_{5}}=11$ چند جواب صحیح و مثبت دارد؟ $({{x}_{i}}\ge 1\,,\,1\le i\le 5)$
5- معادلهٔ ${{x}_{1}}+{{x}_{2}}+....{{x}_{6}}=12$ چند جواب صحیح و مثبت دارد به شرط آنکه ${{x}_{3}}=4$ و ${{x}_{5}}\gt 2$ باشد؟
مربعهای لاتین
سه مدرس به نامهای احمدی، کریمی و عباسی قصد دارند در یک روز در سه جلسه 10-8، 12-10 و 4-2 در سه کلاس A، B و C تدریس کنند. هر کلاس سه جلسهٔ درسی خواهد داشت و هر مدرس در هر یک از کلاسها دقیقاً یکبار باید تدریس کند. نام مدرسها را در جدول زیر بهگونهای وارد کنید که شرایط خواسته شده محقق گردد.
| کلاس / جلسات | 8-10 | 10-12 | 2-4 | |
|---|---|---|---|---|
| A | ||||
| B | ||||
| C | ||||
فعالیت (صفحهٔ 62 کتاب درسی)
1- بهجای نام سه مدرس مذکور بهترتیب اعداد 1، 2 و 3 را قرار دهید و یک جدول $3\times 3$ از اعداد بهدست آورید.
2- موارد معادل در دو ستون چپ و راست را به هم وصل کنید.
| الف) در هیچ سطری عدد تکراری نداریم. ب) در هیچ ستونی عدد تکراری نداریم. پ) هر یک از اعداد در تمام سطرها آمده است. ت) هر یک از اعداد در تمام ستونها آمده است. |
a) هیچ مدرسی در یک جلسه موظف به تدریس در دو کلاس نشده است. b) هر یک از مدرسین در تمام کلاسها تدریس داشته است. c) هیچ مدرسی در یک کلاس دوبار تدریس نکرده است. d) هر یک از مدرسین در هر یک از جلسهها تدریس داشته است. |
مثال: دو مربع لاتین $3\times 3$ و دو مربع لاتین $4\times 4$ در زیر نمایش داده شده است.
|
|
|
|
|
|
کار در کلاس (صفحهٔ 63 کتاب درسی)
1- دو مربع لاتین $5\times 5$ بنویسید.
2- با استدلال کلامی بگویید که چرا با تعویض جای دو سطر (دو ستون) از یک مربع لاتین شکل حاصل باز هم یک مربع لاتین است؟
3- شکل زیر یک مربع لاتین $n\times n$ است که به آن «مربع لاتین چرخشی» میگوییم. مربع لاتین بودن آن را چگونه توجیه میکنید؟
با توجه به آنچه در کار در کلاس دیدیم برای هر عدد طبیعی مانند n، مربع لاتین $n\times n$ وجود دارد؟
حال فرض کنیم یک مربع لاتین مانند شکل زیر داریم و با اعمال یک جایگشت بر روی 1، 2، 3، ... و n یک مربع جدید بهدست آوردهایم. خواهیم دید که مربع بهدست آمده نیز یک مربع لاتین خواهد بود، زیرا در غیر اینصورت در سطر یا ستونی از مربع جدید عضو تکراری وجود خواهد داشت که این موضوع با توجه به خواص جایگشت ایجاب میکند که در سطر یا ستونی از مربع اوّل نیز عضو تکراری وجود داشته باشد و این با مربع لاتین بودن آن در تناقض است.
کار در کلاس (صفحهٔ 64 کتاب درسی)
برای هر یک از مربعهای لاتین زیر یک جایگشت مشخص نمایید. سپس برای هر یک از جایگشتها از روی مربع لاتین داده شده یک مربع لاتین بهدست آورید.
|
|
|
|
دو مربع لاتین متعامد
بهطور مثال برای دو مربع A و B بهصورت زیر داریم:
یک محک برای تشخیص متعامد بودن دو مربع لاتین بدین صورت است که برای متعامد بودن باید هر دو جایگاه (درایه) در یکی از مربعها که اعداد یکسانی دارند، جایگاههای (درایههای) نظیر به آنها از مربع دیگر اعداد متمایزی داشته باشند. این محک معمولاً زمانیکه میخواهیم نشان دهیم دو مربع لاتین متعامد نیستند بهکار میرود. به این صورت که کافی است در یکی از دو مربع دو درایهٔ یکسان پیدا کنیم بهطوریکه در جایگاههای نظیر به این دو درایه در مربع دیگر نیز درایههای یکسان (یکسان با هم و نه لزوماً یکسان با درایههای مربع اوّل) وجود داشته باشد.
به طور مثال در شکل زیر اگر در مربع لاتینِ A دو عدد یکسان (مانند a در شکل) به گونهای بیابیم که در جایگاههای متناظر با آنها در مربع لاتینِ B (جایگاههای هاشور خورده) نیز اعداد یکسانی باشند، مثلاً خانههای هاشور خورده هر دو حاوی عدد b باشند در این صورت دو مربع A و B متعامد نیستند.
مثال: در هر مورد متعامد بودن دو مربع لاتین داده شده را بررسی کنید.
|
|
حل: الف) مربع حاصل از کنار هم قرار دادن درایههای دو مربع داده شده بهصورت زیر است و چون عدد دو رقمی تکراری در آن نیست لذا دو ماتریس داده شده متعامدند.
ب) خیر، متعامد نیستند؛ زیرا مثلاً جایگاه سطر اول ستون اول و جایگاه سطر دوم ستون دوم در مربع اول درایههای یکسان (هر دو عدد یک هستند) دارند و دو مربع دوم نیز درایههای یکسان (هر دو عدد 3 هستند) دارند.
پ) خیر، متعامد نیستند؛ زیرا مثلاً جایگاه سطر اول ستون دوم و جایگاه سطر چهارم ستون اول در مربع اول درایههای یکسان (هر دو عدد 2 هستند) دارند و در مربع دوم نیز درایههای یکسان (هر عدد 2 هستند) دارند.
کار در کلاس (صفحهٔ 66 تا 67 کتاب درسی)
1- چند مربع لاتین $1\times 1$ وجود دارد؟
2- آیا دو مربع لاتین $2\times 2$ متعامد وجود دارد؟
3- بررسی کنید که آیا دو مربع لاتین $3\times 3$ زیر متعامدند؟
4- آیا دو مربع لاتین $4\times 4$ زیر متعامدند؟
دیدیم که برای 2 و $n=1$، دو مربع لاتین متعامد $n\times n$ وجود ندارد. ثابت شده است که اگر 6 و 2 و $n\ne 1$ دو مربع لاتین متعامد از مرتبهٔ n وجود دارد و برای 6 و 2 و $n=1$ دو مربع لاتین متعامد از مرتبهٔ n وجود ندارد.
5- با انجام یک جایگشت دلخواه برای اعضای B، مربع لاتین جدیدی بهدست آورید و آنرا ${B}'$ بنامید. بررسی کنید که آیا A و ${B}'$ متعامدند؟
مثال: نشان دهید اگر دو مربع لاتین متعامد باشند، مربع لاتینی که با جایگشت بر روی اعضای یکی از آنها بهدست میآید نیز با مربع لاتینِ دیگر متعامد است؛ به عبارتی اگر A و B دو مربع لاتین متعامد باشند و ${{B}_{2}}$ مربع لاتین حاصل از اعمال یک چایگشت بر اعضای B باشد، آنگاه $A$ و ${{B}_{2}}$ نیز متعامدند.
حل: فرض $A$ و ${{B}_{2}}$ متعاود نباشند. لذا دو جایگاه در مربع $A$ وجود دارد که اعداد یکسانی (مثلاً $a$) در آنها قرار دارد و در جایگاههای نظیر آنها در مربع ${{B}_{2}}$ نیز دو درایهٔ یکسان (مثلاً $b$) قرار دارند.
حال با توجه به تعریف جایگشت در همین دو جایگاه در مربع B نیز باید دو درایه یکسان مانند c باشد که در مربع ${{B}_{2}}$ با اعمال جایگشت به درایهٔ b تبدیل شدهاند و در اینصورت دو مربع A و B نیز متعامد نخواهند بود و این با فرض مسئله در تناقض است. لذا A و ${{B}_{2}}$ هم نمیتوانند متعامد نباشند.
مثال: قرار است 5 کارگر با 5 نوع ماشین نخریسی و 5 نوع الیاف در 5 روز هفته کار کنند بهگونهای که هر کارگر با هر نوع ماشین و هر نوع الیاف دقیقاً یکبار کار کرده باشد و نیز هر الیاف در هر ماشین دقیقاً یکبار بهکار گرفته شود. برای این مسئله برنامهریزی کنید.
الف) ابتدا فرض کنید بخواهیم برایِ کارِ 5 کارگر با 5 ماشین ریسندگی 5 ماشین ریسندگی در 5 روز هفته بهگونهای برنامهریزی کنیم که هر کارگر در هر روز با یک ماشین ریسندگی و در طول هفته با هر دستگاه دقیقاً یکبار کار کرده باشد.
برای حل این مسئله میتوانیم از یک مربع لاتین $5\times 5$ استفاده کنیم. فرض کنید هر ستون نشاندهنده یک کارگر و هر سطر نشاندهنده یک روز هفته و هر کدام از اعدادِ 1 و 2 و ... و 5 که در مربع لاتین ظاهر شدهاند نمایانگر یکی از ماشینهای ریسندگی باشند. بنابراین مثلاً در روز دوشنبه کارگر ${{W}_{1}}$ با ماشین ریسندگی شماره 2 کار میکند.
ب) حال فرض کنید که در مسئله مطرح شده در قسمت (الف) 5 نوع الیاف مختلف هم وجود داشته باشد و بخواهیم بهگونهای برنامهریزی کنیم که هر کارگر از هر نوع الیاف هم دقیقاً یکبار استفاده کند.
برای این کار مانند قسمت (الف) یک مربع لاتین می کشیم و هر ستون را نشاندهندهٔ یک کارگر و هر سطر را نشاندهندهٔ یک روز هفته و هر کدام از اعداد 1 و 2 و ... و 5 را که در مربع لاتین ظاهر شدهاند نمایانگر یکی از انواع الیاف در نظر میگیریم. با توجه به مربع لاتین، مثلاً در روز سه شنبه کارگر شمارهٔ 4 با الیاف شمارهٔ 3 کار میکند.
پ) حال اگر درایههای نظیر از دو مربع A و B را در کنار هم در یک مربع جدید قرار دهیم یک مربع $5\times 5$ به شکل زیر خواهیم داشت و میتوانیم تمام اطلاعات فوق را از همین مربع استخراج کنیم. بهطور مثال کارگر شمارهٔ 4 در روز یکشنبه با ماشین شمارهٔ 3 و الیاف شمارهٔ 4 کار میکند. تا اینجا برنامهریزی ما با استفاده از دو مربع لاتین انجام شده است، اما دو مربع لاتین A و B متعامد هم هستند و این ویژگی آنها تا اینجا به کار نیامده است. میدانیم که متعامد بودن دو مربع A و B به این معناست که مربع دو رنگِ حاصل، در هیچ خانهای عدد دو رقمی تکراری ندارد. از آنجا که اعداد سمت چپ شمارهٔ ماشین ریسندگی و اعداد سمت راست شمارهٔ الیاف مورد استفاده هستند لذا در صورتیکه دو مربع استفاده شده متعامد باشند هر الیاف در هر ماشین دقیقاً یکبار بهکار رفته است.
کار در کلاس (صفحهٔ 69 کتاب درسی)
1- در قسمت (الف) از مثال قبل، چرا میتوان مطمئن بود که هر کارگر در طول هفته با هر دستگاه دقیقاً یکبار کار کرده است؟
2- در قسمت (ب) از مثال قبل، چرا میتوان مطمئن بود که هر کارگر با هر یک از الیافها دقیقاً یکبار کار میکند.
3- در قسمت (پ) از مثال قبل، چرا میتوان مطمئن بود که هر یک از الیافها در هر یک از ماشینهای ریسندگی دقیقاً یکبار بهکار گرفته شده است؟
4- اگر سه برادرِ تقریباً هم سن و سال در خانه سه کت و سه پیراهن داشته باشند و بخواهند در سه روز اوّل هفته از این لباسها بهگونهای استفاده کنند که هر فرد هر یک از کتها و هر یک از پیراهنها را دقیقاً یکبار استفاده کرده باشد و هر کت با هر پیراهن نیز دقیقاً یک بار مورد استفاده قرار بگیرد، چگونه میتوانند این کار را انجام دهند؟
یک روش برای ساختن دو مربع لاتین متعامد از مرتبۀ یک عدد فرد
با انجام مراحل زیر می توانید دو مربع لاتین $5\times 5$ متعامد بهدست آورید.
1- اعداد 1، 2، ... و 5 با نظمی خاص (به نحوهٔ چینش اعداد دقت کنید) در دو شکل (الف) و (ب) چیده شدهاند.
|
|
2- حال مربعهای پررنگ $5\times 5$ وسط را در نظر بگیرید و با انتقال اعداد خارج از این مربعها به داخل آنها با روش زیر، مربعها را پر کرده، دو مربع لاتین متعامد از مرتبهٔ 5 به دست آورید.
الف) در هر کدام از مربعها، هر عدد که در سمت چپ آن واقع است را 5 خانه بهسمت راست انتقال دهید.
ب) در هر کدام از مربعها، هر عدد که در سمت راست آن واقع است را 5 خانه بهسمت چپ انتقال دهید.
پ) در هر کدام از مربعها، هر عدد که در بالای مربع واقع است را 5 خانه به پایین انتقال دهید.
ت) در هر کدام از مربعها، هر عدد که در پایین مربع واقع است را 5 خانه به بالا انتقال دهید.
3- با روشی کاملاً مشابه آنچه دیدید برای هر n فرد میتوانید دو مربع لاتین متعامد از مرتبهٔ n بهدست آورید.
تمرین (صفحهٔ 71 تا 72 کتاب درسی)
1- میخواهیم 8 نفر را که دو به دو برادر یکدیگرند در دو طرفِ طولِ یک میز مستطیل شکل بنشانیم. اگر بخواهیم هر نفر روبهروی برادرش بنشیند، به چند طریق میتوان این کار را انجام داد؟
2- اگر داشته باشیم $A=\left\{ 1,2,3,4 \right\}$ و $B=\left\{ 5,6,7,8,9 \right\}$، در انصورت چند رمز یا کد 5 رقمی میتوان نوشت که هر یک شامل دو رقم از A و سه رقم از B باشد؟
3- 4 کتاب فیزیک متفاوت و 5 کتاب ریاضی متفاوت را میتوانیم به چند طریق در قفسهای و در یک ردیف بچینیم. به نظر شما، این عمل به چند روش امکانپذیر است؟ اگر:
الف) هیچ محدودیتی نباشد؛
ب) همواره کتاب های فیزیک کنار هم باشند؛
پ) هیچ دو کتاب ریاضی کنار هم نباشند؛
ت) یک کتاب ریاضیِ خاص و دو کتاب فیزیک خاص همواره کنار هم باشند.
4- برای کنار هم قرار گرفتن 4 دانشآموز پایهٔ دوازدهم و 6 دانشآموز پایهٔ یازدهم مسئلهای طرح کنید که پاسخ آن $7!\times 4!$ باشد.
5- با ارقام 5، 6، 7، 7، 5 و 7 چه تعداد کد 6 رقمی میتوان نوشت؟
6- میخواهیم روی تعدادی جعبهٔ حاوی اجناس تولید شدهٔ خاصی را کدگذاری و هر جعبه را با یک کد، شاملِ 9 حرفِ $d,d,d,c,c,a,b,a,a$، از بقیه مجزا کنیم. حداکثر چند جعبه را میتوانیم با این کدها از بقیه مجزا کنیم؟
7- نفر به چند طریق میتوانند در دو اتاق دونفره و یک اتاق سه نفره قرار بگیرند؟
8- به چند طریق میتوان از بین 5 نوع گل 11 شاخه گل انتخاب کرد اگر بخواهیم:
الف) به دلخواه انتخاب کنیم؛
ب) از هر نوع گل حداقل 1 شاخه انتخاب کنیم؛
پ) از گل نوع دوم حداقل دو شاخه و از گل نوع پنجم بیش از سه شاخه انتخاب کنیم؛
ت) از گل نوع سوم انتخاب نکرده و از گل نوع چهارم حداقل 5 شاخه انتخاب کنیم.
9- مطلوب است تعداد جوابهای صحیح و نامنفی هر یک از معادلات زیر با شرطهای داده شده:
${{x}_{1}}+{{x}_{2}}+...+{{x}_{5}}=10\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{i}}\gt 0\,,\,2\le i\le 5$ (الف
${{x}_{1}}+{{x}_{2}}+...+{{x}_{6}}=12\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{1}}\gt 2\,,\,{{x}_{5}}\ge 4$ (ب
${{x}_{1}}+{{x}_{2}}+...+{{x}_{5}}=11\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{i}}\gt 1\,,\,1\le i\le 5$ (پ
${{x}_{1}}+3{{x}_{2}}+{{x}_{3}}+{{x}_{4}}=7\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{i}}\gt 0\,,\,1\le i\le 4$ (ت
${{x}_{1}}+\sqrt{{{x}_{2}}}+{{x}_{3}}+{{x}_{4}}=3\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{i}}\gt 0\,,\,1\le i\le 4$ (ث
10- به چند طریق میتوان 5 توپ یکسان را بین 3 نفر و به دلخواه توزیع کرد؟
11- به چند طریق میتوان 8 توپ یکسان را بین 4 نفر توزیع کرد هرگاه بخواهیم هر نفر حداقل یک توپ داشته باشد؟
12- آیا مربع لاتینِ حاصل از اعمال یک جایگشت روی اعضای یک مربع لاتین دلخواه میتواند با مربع اولیه متعامد باشد؟
13- مربع لاتین $3\times 3$ زیر را در نظر بگیرید.
الف) سطر دوم و سوم مربع A را جابهجا کنید و مربع حاصل را ${{A}_{1}}$ بنامید. آیا $A$ و ${{A}_{1}}$ متعامدند؟
ب) ابتدا سطِر اول و سطِر سوم مربع A را جابهجا کنید. سپس در مربع حاصل، سطر دوم و سوم را جابهجا کنید و مربع حاصل را را ${{A}_{2}}$ بنامید. آیا $A$ و ${{A}_{2}}$ متعامدند؟
پ) با توجه به قسمتهای (الف) و (ب) به سؤالات زیر جواب دهید.
1- آیا میتوان گفت با تعویض جای سطرهای یک مربع لاتین، همواره مربع لاتینی متعامد با مربع لاتین اول بهدست میآید؟
2- آیا میتوان گفت با تعویض جای سطرهای یک مربع لاتین، همواره مربع لاتینی غیرمتعامد با مربع لاتین اول بهدست میآید؟
14- قرار است شش مدرس ${{T}_{1}}$، ${{T}_{2}}$، ... و ${{T}_{6}}$ در شش جلسهٔ متوالی در شش کلاسِ ${{C}_{1}}$، ${{C}_{2}}$، ... و ${{C}_{6}}$ بهگونهای تدریس کنند که هر مدرس در هر کلاس دقیقاً یک جلسه تدریس کند. برای این منظور برنامهریزی نمایید.
15- دو مربع لاتین متعامد از مرتبهٔ 3 و دو مربع لاتین متعامد از مرتبهٔ 7 بنویسید.
16- در یک مسابقهٔ اتومبیلرانی قرار است 7 راننده در هفت روزِ هفته با هفت ماشین مختلف در هفت مسیر مختلف مسابقه دهند بهطوریکه شرایط زیر برقرار باشد:
الف) هر راننده هر روز با یک ماشین در یک مسیر رانندگی کند؛
ب) هر راننده با هر ماشین دقیقاً یک روز رانندگی کند؛
پ) هر راننده هر روز دقیقاً در یک مسیر رانندگی کند؛
ت) هر ماشین در هر مسیر دقیقاً یک بار بهکار گرفته شود.
- برای این منظور یک برنامهریزی انجام دهید.